package 强化训练;

import java.util.Scanner;

public class day19最长公共字串 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextLine()){
            String s1 = sc.next();
            String s2 = sc.next();
            System.out.println(help(s1,s2));
            System.out.println(findMaxLenStr(s1,s2));
        }

    }

    /**
     * 任意两个字符串的中，最长的公共部分
     * @param s1
     * @param s2
     * @return
     */
    private static String help(String s1,String s2){
        int sta = 0;
        int end = 0;
        int maxLen = 0;
        String res = "";
        for(int i = 0; i < s1.length();i++){
            for(int j = 0;j < s2.length() ; j++){
                int k = i;
                if(s1.charAt(k) != s2.charAt(j)){
                    continue;
                }else{
                    sta = j;//如果出现了相等位置，此时记录开始位置；
                    end = j;//end递增
                    while(k < s1.length() && end < s2.length() && s1.charAt(k) == s2.charAt(end)){
                        k++;
                        end++;
                    }
                    //循环结束，1与2不等，
                    if(maxLen < (end - sta)){
                        maxLen = end - sta;
                        res = s2.substring(sta,end);
                    }
                }
            }
        }
        return res;
    }

    /**
     * 传入两个字符串，返回两个字符串的最长公共字串
     * @param str1 字符串1，默认比str2短
     * @param str2
     * @return 返回str1中和str2连续共同的部分
     */
    private static String findMaxLenStr(String str1 ,String str2){
        int len1 = str1.length();
        int len2 = str2.length();
        char[] ch1 = str1.toCharArray();
        char[] ch2 = str2.toCharArray();
        int[][] dp = new int[len1+1][len2+1];//dp状态容器
        int maxLen = 0;//最长字串的长度
        int end = 0;//最长字串的末尾下标

        //初始化
        for (int i = 0; i < len1+1; i++) {
            dp[i][0] = 0;//第一列全置为0
        }
        for (int i = 0; i < len2+1; i++) {
            dp[0][i] = 0;//第一行全置为0
        }

        //填表
        for (int i = 1; i < len1+1; i++) {
            for (int j = 1; j < len2+1; j++) {
                if (ch1[i-1] == ch2[j-1]){
                    dp[i][j] = dp[i-1][j-1] + 1;//如果当前两个位置元素相等，当前位置的长度为前i-1，和j-1个位置的长+1；
                    if (maxLen < dp[i][j]){
                        maxLen = dp[i][j];
                        end = i;
                    }
                }
            }
        }

        //返回值，返回str1的end-maxlen 到 end的位置
        return str1.substring(end-maxLen,end);
    }
}
